Various data storage systems employ multiple storage devices, such as Hard Disk Drives (HDD), Solid State Disks (SSD) or solid-state memory devices, for storing data. Several techniques have been developed for storing data reliably, and for recovering from storage device failures. For example, Redundant Array of Inexpensive Disks (RAID) is a family of storage schemes, which store data redundantly and enable recovery from a failure of one or more of the storage devices.
As another example, U.S. Patent Application Publication 2008/0115017, whose disclosure is incorporated herein by reference, describes fault-tolerant, redundancy-based data-storage systems. These techniques use disk-controller-implemented error detection and error correction, at the disk-block level, and RAID-controller-implemented data-redundancy methods, at the disk and disk-stripe level, in order to provide error detection and error correction.
U.S. Patent Application Publication 2002/0174295, whose disclosure is incorporated herein by reference, describes a file system that includes a plurality of disk drives for storing parity groups, each parity group comprising storage blocks. The storage blocks include one or more data blocks and a parity block associated with the data blocks. Each of the storage blocks is stored on a separate disk drive such that no two storage blocks from a given parity group reside on the same disk drive. A recovery module dynamically recovers data lost when a disk drive becomes unavailable. The recovery module produces a reconstructed block by using information in the remaining storage blocks of a parity group corresponding to an unavailable storage block, and stores the reconstructed block on a functioning drive.
U.S. Patent Application Publication 2008/0209304, whose disclosure is incorporated herein by reference, describes a redundant array of independent devices, which uses convolution encoding to provide redundancy of the striped data written to the devices. No parity is utilized in the convolution encoding process. Trellis decoding is used for both reading the data from the array and for rebuilding missing encoded data from one or more failed devices, based on a minimal, and preferably zero, Hamming distance for selecting the connected path through the trellis diagram.